package com.Questions.DP;


/**
 *  最小路径和
 */
public class leetcode64 {
    // 给定一个m*n的网格 每次只能向下挥着向右移动一步
    // 因为第一行只能向右移动才能达到
    // 第一列 只能向左移动才能达到
    // 因此 这些元素的最小路径和为对应路径上的数字总和

    // 不是第一行也不是第一列的网格 可以通过向右 或者向下移动得到
    // 其最短路径和是
    // 其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值
    // 因此可以使用动态规划求解

    // 创建二维数组 dp[0][0]=grid[0][0]
    // i>0 j=0 第一列 dp[i][0]=dp[i-1][0]+grid[i][0]
    // i=0 j>0 第一行 dp[0][j]=dp[0][j-1]+grid[0][j]
    // i>0 j>0 dp[][]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]

    public int minPathSum(int[][] grid) {
        int row=grid.length;
        int clo=grid[0].length;
        int[][] dp=new int[row][clo];
        // 将动态规划的矩阵边界初始化
        dp[0][0]=grid[0][0];
        for(int i=1;i<row;++i){
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for(int j=1;j<clo;++j){
            dp[0][j]=dp[0][j-1]+grid[0][j];
        }
        for(int i=1;i<row;++i){
            for(int j=1;j<clo;++j){
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[row-1][clo-1];
    }
}
